home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 August: Tool Chest / Dev.CD Aug 00 TC Disk 2.toast / pc / sample code / processes / mp threaded sort / heapsort.cp < prev    next >
Encoding:
Text File  |  2000-06-23  |  2.1 KB  |  94 lines
  1. /*
  2.     File:        HeapSort.cp
  3.  
  4.     Contains:     Apply a Heap Sort Algorithm to an offscreen, scrambled GWorld
  5.  
  6.     Written by:     
  7.  
  8.     Copyright:    Copyright © 1988-1999 by Apple Computer, Inc., All Rights Reserved.
  9.  
  10.                 You may incorporate this Apple sample source code into your program(s) without
  11.                 restriction. This Apple sample source code has been provided "AS IS" and the
  12.                 responsibility for its operation is yours. You are not permitted to redistribute
  13.                 this Apple sample source code as "Apple sample source code" after having made
  14.                 changes. If you're going to re-distribute the source, we require that you make
  15.                 it clear in the source that the code was descended from Apple sample source
  16.                 code, but that you've made changes.
  17.  
  18.     Change History (most recent first):
  19.                 7/27/1999    Karl Groethe    Updated for Metrowerks Codewarror Pro 2.1
  20.                 
  21.  
  22. */
  23. #include "SortPicts.h"
  24.  
  25. void HeapSort( SortPicts *sortPicts)
  26. {
  27.     sortPicts->HeapSort();
  28. }
  29.  
  30. /*************************************************************/
  31. /*                                                           */
  32. /*               The Actual Sort Algorithms                  */
  33. /*                                                           */
  34. /*************************************************************/
  35.  
  36. void    SortPicts::HeapSort( void)
  37. {
  38.     
  39.     long            loop;
  40.     long            size;
  41.     
  42.     BuildHeap();
  43.     
  44.     size = N - 1;
  45.     for( loop = N-1; loop; --loop)
  46.     {
  47.         ExchangeSortItem( 0, loop);
  48.         
  49.         Heapify( --size, 0);
  50.     }        
  51. }
  52.  
  53. void    SortPicts :: BuildHeap( void)
  54. {
  55.     long        loop;
  56.  
  57.     for( loop = (N>>1)+3; loop; --loop)
  58.         Heapify( N-1, loop -1);
  59. }
  60.  
  61. //
  62. //        This code adjusts for a zerø based array
  63. //        (Where as the original source from Sedgewick (good book)
  64. //        was 1..N, not 0..N-1
  65. //
  66.  
  67. #define        Left(i)            (((i+1) << 1) -2)
  68. #define        Right(i)        (((i+1) << 1) -1)
  69.  
  70. void    SortPicts :: Heapify( long size, long index)
  71. {
  72.     long    left, right, largest;
  73.     
  74.     left = Left( index);
  75.     right = Right( index);
  76.     
  77.     largest = index;
  78.     
  79.     if( left <= size)
  80.         if( sortData[left] > sortData[index])
  81.             largest = left;
  82.     
  83.     if( right <= size)
  84.         if( sortData[right] > sortData[largest])
  85.             largest = right;
  86.     
  87.     if( largest != index)
  88.     {
  89.         ExchangeSortItem(index, largest);
  90.         Heapify( size, largest);
  91.     }
  92. }
  93.  
  94.